package leetcode.editor.cn1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 * <p>
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 * <p>
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 */
public class FindContinuousSequence {

    public static void main(String[] args) {
        Solution solution = new FindContinuousSequence().new Solution();
        System.out.println(solution.findContinuousSequence(15));
    }

    class Solution {
        public int[][] findContinuousSequence(int target) {
            if (target == 1)
                return new int[][]{{1}};
            int mid = target % 2 == 0 ? target / 2 : target / 2 + 1;
            List<Queue<Integer>> list = new ArrayList<>();
            for (int i = 0; i <= mid; i++) {
                Queue<Integer> queue = new LinkedList<>();
                int tmp = target;
                for (int j = i + 1; j <= mid; j++) {
                    tmp = tmp - j;
                    if (tmp > 0) {
                        queue.offer(j);
                    } else if (tmp == 0) {
                        queue.offer(j);
                        list.add(queue);
                        break;
                    } else if (tmp < 0) {
                        break;
                    }
                }
            }

            int[][] res = new int[list.size()][];
            int nlen = list.size();
            for (int i = 0; i < nlen; i++) {
                Queue<Integer> queue = list.get(i);
                int clen = queue.size();
                res[i] = new int[clen];
                for (int j = 0; j < clen; j++) {
                    int poll = queue.poll();
                    System.out.println(poll);
                    res[i][j] = poll;
                }
            }
            return res;
        }
    }
}
